/**
 * 312. 戳气球
 * https://leetcode-cn.com/problems/burst-balloons/
 */

// let dp;
// let cache;
//
// /**
//  * @param {number} i
//  * @param {number} j
//  * @return {number}
//  */
// function completeDP(i, j) {
//   if (i >= j - 1) {
//     return 0;
//   }
//   if (dp[i][j] >= 0) {
//     return dp[i][j];
//   }
//   let max = 0;
//   for (let mid = i + 1; mid < j; mid += 1) {
//     const count = cache[mid] * cache[i] * cache[j] + completeDP(i, mid) + completeDP(mid, j);
//     if (count > max) {
//       max = count;
//     }
//   }
//   dp[i][j] = max;
//   return dp[i][j];
// }
//
// /**
//  * 记忆法
//  * @param {number[]} nums
//  * @return {number}
//  */
// function maxCoins(nums) {
//   const size = nums.length + 2;
//   cache = [1, ...nums, 1];
//   dp = new Array(size);
//   for (let i = 0; i < size; i += 1) {
//     dp[i] = new Array(size).fill(-1);
//   }
//   completeDP(0, size - 1);
//   return dp[0][size - 1];
// }

/**
 * 动态规划法
 * @param {number[]} nums
 * @return {number}
 */
function maxCoins(nums) {
  const size = nums.length + 2;
  const cache = [1, ...nums, 1];
  const dp = new Array(size);
  for (let i = 0; i < size; i += 1) {
    dp[i] = new Array(size).fill(0);
  }
  for (let i = size - 3; i >= 0; i -= 1) {
    for (let j = i + 2; j < size; j += 1) {
      for (let mid = i + 1; mid < j; mid += 1) {
        dp[i][j] = Math.max(
          dp[i][j],
          cache[i] * cache[mid] * cache[j] + dp[i][mid] + dp[mid][j],
        );
      }
    }
  }
  return dp[0][size - 1];
}

console.log(maxCoins([3, 1, 5, 8]) === 167);
console.log(maxCoins([1, 5]) === 10);
console.log(maxCoins([2]) === 2);
console.log(maxCoins([3, 0]) === 3);
console.log(maxCoins([9, 76, 64, 21, 97, 60, 5]) === 1088290);
